近邻粒子搜索

网格方法中网格间的拓扑关系一般是不变的，但粒子法中粒子有规则无序运动时，粒子间的拓扑关系需要被建立， 这涉及到最近相邻粒子搜索。近邻粒子搜索是 SPH 等粒子法的核心算法，其时间复杂度将直接影响到程序的运行效率。

常见的粒子搜索法有背景网格法、树型搜索法、直接搜索法。如著名的分子动力学开源软件 LAMMPS， 采用的时间复杂度最低的背景网格法，本仓库也采用的是背景网格法，结合了无边界依赖的哈希映射。即使是背景网格法， NNPS的建立与搜索也将占用全运行时长过半的耗时。换言之, 在无法提高 NNPS 效率前， 增加核心计算部分内容将有可能不会显著增加耗时。

SPX 采用背景网格链表近邻搜索，其实际时间复杂度略高于 O(n)。 假设粒子间距与光滑长度一致的情况下，背景网格边长需要满足：scale∗hsml<=c。 近邻搜索的正确性由构建背景网格与紧支域一同确定！ SPH 算法除了近邻搜索可能花费较多时间（建立、查询、销毁）。

哈希函数

通常，哈希映射能避免对空背景网格的存储和访问，既能节省内存，又提高运行效率，动态适应粒子分布，但提高了散列性。

cell(x,y,z,h)=(x,y,z)h=(i,j,k)

其中，p1=73856093, p2=19349663, p3=83492791, m 是设置哈希表的大小，推荐取为1~2倍的粒子数。

链接

• CFD粒子法中NNPS的经典方案实现.

这是我在编写 SPX 时，抽象出来的 NNPS 模块算法，包含了背景网格法、树型搜索法、直接搜索法，其中 2~3 维的背景网格法受到了高度优化。